home *** CD-ROM | disk | FTP | other *** search
/ Tech Arsenal 1 / Tech Arsenal (Arsenal Computer).ISO / tek-19 / iritsm3s.zip / PRIORQUE.C < prev    next >
C/C++ Source or Header  |  1992-01-12  |  11KB  |  299 lines
  1. /*****************************************************************************
  2. * PriorQue.c - implement priority queue, using regular binary trees         *
  3. * (that guarantees only average time of NlogN...) and with the following     *
  4. * operations:                                     *
  5. * 1. PQInit(&PQ) - initialize the queue, must be called before usage.         *
  6. * 2. PQEmpty(PQ) - returns TRUE iff PQ is empty.                 *
  7. * 3. PQCompFunc(&CompFunc) - sets (a pointer to) the function that is         *
  8. *    used to compere two items in the queue. the function should get two     *
  9. *    item pointers, and should return >1, 0, <1 as comparison result for     *
  10. *    greater than, equal, or less than respectively.                 *
  11. * 4. PQFirst(&PQ, Delete) - returns the first element of the priority         *
  12. *    queue, and delete it from queue if delete is TRUE.                 *
  13. * 5. PQInsert(&PQ, NewItem) - insert NewItem into the queue             *
  14. *    (NewItem is a pointer to it), using the comparison function CompFunc.   *
  15. * 6. PQDelete(&PQ, OldItem) - Delete old item from the queue             *
  16. *    again using the comparison function CompFunc.                 *
  17. * 7. PQFind(PQ, OldItem)  - Find old item in queue, again using the         *
  18. *    comparison function CompFunc.                         *
  19. * 8. PQNext(PQ, CmpItem, NULL) - returns the smallest item which is bigger   *
  20. *    than given item CmpItem. PQ is not modified. Return NULL if none.         *
  21. * 9. PQPrint(PQ, &PrintFunc) - print the queue in order using the given      *
  22. *    printing function PrintFunc.                         *
  23. *10. PQFree(&PQ, FreeItems) - Free the queue. The items are also freed if    *
  24. *    FreeItems is TRUE.                                 *
  25. *                                         *
  26. *             Written by Gershon Elber,   Dec 88                   *
  27. *****************************************************************************/
  28.  
  29. #include <stdio.h>
  30. #include <string.h>
  31. #include "irit_sm.h"
  32. #include "priorque.h"
  33.  
  34. #define PQ_NEW_NODE(PQ)  { \
  35.     PQ = (PriorQue *) malloc(sizeof(PriorQue)); \
  36.     (PQ) -> Right = (PQ) -> Left = NULL; \
  37.     (PQ) -> Data = NULL; }
  38. #define PQ_FREE_NODE(PQ) { free((char *) (PQ)); PQ = NULL; }
  39.  
  40. static PQCompFuncType CompFunc = (PQCompFuncType) strcmp;
  41.  
  42. /******************************************************************************
  43. * PQEmpty - initialize the queue...                          *
  44. ******************************************************************************/
  45. void PQInit(PriorQue **PQ)
  46. {
  47.     *PQ = NULL;
  48. }
  49.  
  50. /******************************************************************************
  51. * PQEmpty - returns TRUE iff PQ priority queue is empty.              *
  52. ******************************************************************************/
  53. int PQEmpty(PriorQue *PQ)
  54. {
  55.     return PQ == NULL;
  56. }
  57.  
  58. /******************************************************************************
  59. * PQCompFunc - sets (a pointer to) the function that is used to compere two   *
  60. * items in the queue. The function should get two item pointers, and should   *
  61. * return >1, 0, <1 as comparison result for greater than, equal, or less than *
  62. * respectively.                                      *
  63. ******************************************************************************/
  64. void PQCompFunc(PQCompFuncType NewCompFunc)
  65. {
  66.     CompFunc = NewCompFunc;
  67. }
  68.  
  69. /******************************************************************************
  70. * PQFirst - returns the first element of the priority queue, and delete it    *
  71. * from queue if Delete is TRUE. return NULL if empty queue              *
  72. ******************************************************************************/
  73. VoidPtr PQFirst(PriorQue **PQ, int Delete)
  74. {
  75.     VoidPtr Data;
  76.     PriorQue *Ptemp = (*PQ);
  77.  
  78.     if (*PQ == NULL) return NULL;
  79.  
  80.     while (Ptemp -> Right != NULL)
  81.     Ptemp = Ptemp -> Right;                  /* Find smallest item. */
  82.     Data = Ptemp -> Data;
  83.  
  84.     if (Delete) PQDelete(PQ, Data);
  85.  
  86.     return Data;
  87. }
  88.  
  89. /******************************************************************************
  90. * PQInsert - insert new item into the queue (NewItem is a pointer to it),     *
  91. * using given compare function CompFunc. CompFunc should return >1, 0, <1     *
  92. * as two item comparison result for greater than, equal, or less than         *
  93. * respectively.                                      *
  94. *   Insert is always as a leaf of the tree.                      *
  95. *   Return pointer to old data if was replaced or NULL if the item is new.    *
  96. ******************************************************************************/
  97. VoidPtr PQInsert(PriorQue **PQ, VoidPtr NewItem)
  98. {
  99.     int Compare;
  100.     VoidPtr Data;
  101.  
  102.     if ((*PQ) == NULL) {
  103.     PQ_NEW_NODE(*PQ);
  104.     (*PQ) -> Data = NewItem;
  105.     return NULL;
  106.     }
  107.     else {
  108.     Compare = (*CompFunc)(NewItem, (*PQ) -> Data);
  109.     Compare = SIGN(Compare);
  110.     switch (Compare) {
  111.         case -1:
  112.         return PQInsert(&((*PQ) -> Right), NewItem);
  113.         case 0:
  114.         Data = (*PQ) -> Data;
  115.         (*PQ) -> Data = NewItem;
  116.         return Data;
  117.         case 1:
  118.         return PQInsert(&((*PQ) -> Left), NewItem);
  119.     }
  120.     }
  121.     return NULL;                    /* Makes warning silent. */
  122. }
  123.  
  124. /******************************************************************************
  125. * PQDelete - Delete old item from the queue, again using the comparison       *
  126. * function CompFunc.                                  *
  127. * Returns pointer to Deleted item if was fould and deleted, NULL otherwise.   *
  128. ******************************************************************************/
  129. VoidPtr PQDelete(PriorQue **PQ, VoidPtr OldItem)
  130. {
  131.     int Compare;
  132.     PriorQue *Ptemp;
  133.     VoidPtr Data;
  134.     VoidPtr OldData;
  135.  
  136.     if ((*PQ) == NULL) {
  137.     return NULL;
  138.     }
  139.     else {
  140.     Compare = (*CompFunc)(OldItem, (*PQ) -> Data);
  141.     Compare = SIGN(Compare);
  142.     switch (Compare) {
  143.         case -1:
  144.         return PQDelete(&((*PQ) -> Right), OldItem);
  145.         case 0:
  146.         OldData = (*PQ) -> Data;       /* The returned deleted item. */
  147.  
  148.         if ((*PQ) -> Right == NULL && (*PQ) -> Left == NULL) {
  149.             /* Thats easy - we delete a leaf: */
  150.             Data = (*PQ) -> Data;
  151.             PQ_FREE_NODE(*PQ); /* Note *PQ is also set to NULL here. */
  152.         }
  153.         else if ((*PQ) -> Right != NULL) {
  154.             /* replace this node by the biggest in the Right branch: */
  155.             /* move once to the Right and then Left all the time...  */
  156.             Ptemp = (*PQ) -> Right;
  157.             if (Ptemp -> Left != NULL) {
  158.             while (Ptemp -> Left -> Left != NULL)
  159.                 Ptemp = Ptemp -> Left;
  160.             Data = Ptemp -> Left -> Data;/*Save the data pointer.*/
  161.             PQDelete(&(Ptemp -> Left), Data);  /* Delete recurs. */
  162.             (*PQ) -> Data = Data; /* And put that data instead...*/
  163.             }
  164.             else {
  165.             Data = Ptemp -> Data;      /* Save the data pointer. */
  166.             PQDelete(&((*PQ) -> Right), Data); /* Delete recurs. */
  167.             (*PQ) -> Data = Data; /* And put that data instead...*/
  168.             }
  169.         }
  170.         else {                        /* Left != NULL. */
  171.             /* replace this node by the biggest in the Left branch:  */
  172.             /* move once to the Left and then Right all the time...  */
  173.             Ptemp = (*PQ) -> Left;
  174.             if (Ptemp -> Right != NULL)    {
  175.             while (Ptemp -> Right -> Right != NULL)
  176.                 Ptemp = Ptemp -> Right;
  177.             Data = Ptemp -> Right -> Data; /* Save data pointer. */
  178.             PQDelete(&(Ptemp -> Right), Data);  /*Delete recurs. */
  179.             (*PQ) -> Data = Data; /* And put that data instead...*/
  180.             }
  181.             else {
  182.             Data = Ptemp -> Data;      /* Save the data pointer. */
  183.             PQDelete(&((*PQ) -> Left), Data);  /* Delete recurs. */
  184.             (*PQ) -> Data = Data; /* And put that data instead...*/
  185.             }
  186.         }
  187.         return OldData;
  188.         case 1:
  189.         return PQDelete(&((*PQ) -> Left), OldItem);
  190.     }
  191.     }
  192.     return NULL;                    /* Makes warning silent. */
  193. }
  194.  
  195. /******************************************************************************
  196. * PQFind - Find old item from the queue, again using the comparison          *
  197. * function CompFunc.                                  *
  198. * Returns pointer to item if was fould, NULL otherwise.                  *
  199. ******************************************************************************/
  200. VoidPtr PQFind(PriorQue *PQ, VoidPtr OldItem)
  201. {
  202.     int Compare;
  203.  
  204.     if (PQ == NULL) {
  205.     return NULL;
  206.     }
  207.     else {
  208.     Compare = (*CompFunc)(OldItem, PQ -> Data);
  209.     Compare = SIGN(Compare);
  210.     switch (Compare) {
  211.         case -1:
  212.         return PQFind(PQ -> Right, OldItem);
  213.         case 0:
  214.         return PQ -> Data;
  215.         case 1:
  216.         return PQFind(PQ -> Left, OldItem);
  217.     }
  218.     }
  219.     return NULL;                    /* Makes warning silent. */
  220. }
  221.  
  222. /******************************************************************************
  223. * PQNext - returns the smallest item which is bigger than given item CmpItem. *
  224. * PQ is not modified. Return NULL if none was found.                  *
  225. * BiggerThan will allways hold the smallest Item bigger than current one.     *
  226. ******************************************************************************/
  227. VoidPtr PQNext(PriorQue *PQ, VoidPtr CmpItem, VoidPtr BiggerThan)
  228. {
  229.     int Compare;
  230.     PriorQue *Ptemp;
  231.  
  232.     if (PQ == NULL)
  233.     return BiggerThan;
  234.     else {
  235.     Compare = (*CompFunc)(CmpItem, PQ -> Data);
  236.     Compare = SIGN(Compare);
  237.     switch (Compare) {
  238.         case -1:
  239.         return PQNext(PQ -> Right, CmpItem, PQ -> Data);
  240.         case 0:
  241.         /* Found it - if its right tree is not empty, returns its    */
  242.         /* smallest, else returns BiggerThan...                 */
  243.         if (PQ -> Left != NULL) {
  244.             Ptemp = PQ -> Left;
  245.             while (Ptemp -> Right != NULL) Ptemp = Ptemp -> Right;
  246.             return Ptemp -> Data;
  247.         }
  248.         else
  249.             return BiggerThan;
  250.         case 1:
  251.         return PQNext(PQ -> Left, CmpItem, BiggerThan);
  252.     }
  253.     }
  254.     return NULL;                    /* Makes warning silent. */
  255. }
  256.  
  257. /******************************************************************************
  258. * PQPrint - print the queue in order using the given printing functionq       *
  259. * PrintFunc.                                      *
  260. ******************************************************************************/
  261. void PQPrint(PriorQue *PQ, void (*PrintFunc)(VoidPtr))
  262. {
  263.     if (PQ == NULL) return;
  264.  
  265.     PQPrint(PQ -> Right, PrintFunc);
  266.  
  267.     (*PrintFunc)(PQ -> Data);
  268.  
  269.     PQPrint(PQ -> Left, PrintFunc);
  270. }
  271.  
  272. /******************************************************************************
  273. * PQFree - Free the queue. The items are also freed if FreeItems is TRUE.     *
  274. ******************************************************************************/
  275. void PQFree(PriorQue *PQ, int FreeItem)
  276. {
  277.     if (PQ == NULL) return;
  278.  
  279.     PQFree(PQ -> Right, FreeItem);
  280.     PQFree(PQ -> Left, FreeItem);
  281.  
  282.     if (FreeItem) free((char *) PQ -> Data);
  283.     free((char *) PQ);
  284. }
  285.  
  286. /******************************************************************************
  287. * PQFreeFunc - Free queue. Items are also freed by calling FreeFunc on them.  *
  288. ******************************************************************************/
  289. void PQFreeFunc(PriorQue *PQ, void (*FreeFunc)(VoidPtr))
  290. {
  291.     if (PQ == NULL) return;
  292.  
  293.     PQFreeFunc(PQ -> Right, FreeFunc);
  294.     PQFreeFunc(PQ -> Left, FreeFunc);
  295.  
  296.     (FreeFunc)(PQ -> Data);
  297.     free((char *) PQ);
  298. }
  299.